#define _CRT_SECURE_NO_WARNINGS 1		
//#include <stdio.h>
//int main()
//{
//    int n = 0;
//    while (~scanf("%d", &n))
//    {
//        for (int i = 1; i <= n; i++)
//        {
//            for (int j = 1; j <= n - i; j++)
//            {
//                printf(" ");
//            }
//            for (int j = 1; j <= i; j++)
//            {
//                printf("* ");
//            }
//            printf("\n");
//        }
//    }
//}
//#include <stdio.h>
//int main()
//{
//    int n = 0;
//    while (~scanf("%d", &n))
//    {
//        for (int i = 1; i <= n; i++)
//        {
//            for (int j = 1; j <= i - 1; j++)
//            {
//                printf(" ");
//            }
//            for (int j = 1; j <= n - i + 1; j++)
//            {
//                printf("* ");
//            }
//            printf("\n");
//        }
//    }
//}
//#include <stdio.h>
//int main()
//{
//    int n = 0;
//    while (~scanf("%d", &n))
//    {
//        for (int i = 1; i <= n + 1; i++)
//        {
//            for (int j = 1; j <= n + 1 - i; j++)
//            {
//                printf(" ");
//            }
//            for (int j = 1; j <= i; j++)
//            {
//                printf("* ");
//            }
//            printf("\n");
//        }
//        for (int i = n + 2; i <= 2 * n + 1; i++)
//        {
//            for (int j = 1; j < i - n; j++)
//            {
//                printf(" ");
//            }
//            for (int j = 1; j <= 2 * n + 1 - i + 1; j++)
//            {
//                printf("* ");
//            }
//            printf("\n");
//        }
//    }
//}
//#include<stdio.h>
//#include<string.h>
//int main()
//{
//	char arr[100005] = "a";
//	scanf("%s", arr);
//		for (int i = 1; i < strlen(arr); i++)
//		{
//			int flag = 0;
//			if (arr[i] == arr[i - 1])
//			{
//				flag = 1;
//				for (int j = i+1;; j++)
//				{
//					if (arr[j] != arr[i - 1])
//					{
//						break;
//					}
//					flag++;
//				}
//				for (int j = i; j < strlen(arr); j++)
//				{
//					arr[j] = arr[j + flag];
//				}
//			}
//		}
//		printf("%s\n", arr);
//}
//#include<stdio.h>
//#include<string.h>
//int main()
//{
//	char num[205] = "a";
//	while (~scanf("%s", num))
//	{
//		int len = strlen(num);
//		if (len < 6)
//		{
//			printf("Wrong Message!\n");
//			continue;
//		}
//		else
//		{
//			int flag = 1;
//			for (int i = 0; i < len; i++)
//			{
//				if (num[i] < '0' || num[i]>'9')
//				{
//					printf("Wrong Message!\n");
//					flag = 0;
//					break;
//				}
//			}
//			if (flag)
//			{
//				printf("msg-");
//				for (int i = len - 6; i < len; i++)
//				{
//					printf("%c", num[i]);
//				}
//				printf("\n");
//			}
//		}
//	}
// 
//}
//#include<stdio.h>
//void bajinzhi(int n)
//{
//		if (n > 7)
//		{
//			bajinzhi(n / 8);
//		}
//		printf("%d", n % 8);
//}
//int main()
//{
//	long long int n = 0;
//	while (~scanf("%d", &n))
//	{
//		bajinzhi(n);
//		printf("\n");
//	}
//}
//#include<stdio.h>
//int main()
//{
//	long long int t = 0;
//	scanf("%lld", &t);
//	for (int i = 0; i < t; i++)
//	{
//		long long int n = 0, m = 0;
//		scanf("%lld%lld", &n, &m);
//		long long int arr[100010] = { 0 };
//		for (int j = 0; j < n; j++)
//		{
//			scanf("%d", &arr[j]);
//		}
//	}
//}
//#include<stdio.h>
//int main()
//{
//	int arr[105] = { 2,4 };
//	int n = 0, m = 0;
//	while (~scanf("%d%d", &n, &m))
//	{
//		for (int i = 2; i < n; i++)
//		{
//			arr[i] = arr[i - 1] + 2;
//		}
//		for (int i = 0;i<; i += (n / m))
//		{
//			int sum = 0;
//			for (int j = i;j<i+m; j++)
//			{
//				sum += arr[j];
//			}
//			sum /= m;
//			printf("%d ", sum);
//		}
//		
//		int sum1 = 0;
//		for (int i = n / m+1 ; i < n; i++)
//		{
//			sum1 += arr[i];
//		}
//		sum1 /= (n - n / m -1);
//		printf("%d ", sum1);
//		printf("\n");
//	}
//}
//#include<stdio.h>
//int main()
//{
//	int n = 0,num=1;
//	while (~scanf("%d", &n))
//	{
//		if (n == -1)
//		{
//			break;
//		}
//		int i = 1,sum=1;
//		while(1)
//		{
//			if (n > sum && n <sum * 2)
//			{
//				printf("Case %2d: %2d\n", num, i);
//				break;
//			}
//			if (n == sum)
//			{
//				printf("Case %2d: %2d\n", num, i-1);
//				break;
//			}
//			sum *= 2;
//			i++;
//		}
//		num++;
//	}
//}
//#include <stdio.h>
//int main()
//{
//    char word[105] = "a";
//    scanf("%s", word);
//    int maxn = 0, minn = 1;
//    for (int i = 0; i < strlen(word); i++)
//    {
//        int sum = 0;
//        for (int j = 0; j < strlen(word); j++)
//        {
//            if (word[i] == word[j])
//            {
//                sum++;
//            }
//        }
//        if (sum > maxn)
//        {
//            maxn = sum;
//        }
//        if (sum < minn)
//        {
//            minn = sum;
//        }
//    }
//    int jieguo = maxn - minn;
//    if (jieguo < 2)
//    {
//        printf("No Answer\n%d", jieguo);
//    }
//    else
//    {
//        int flag = 1;
//        for (int j = 2; j < sqrt(jieguo); j++)
//        {
//            if (jieguo % j == 0)
//            {
//                printf("No Answer\n%d", jieguo);
//                int falg = 0;
//                break;
//            }
//        }
//        if (flag)
//        {
//            printf("Lucky Word\n%d", jieguo);
//        }
//    }
//}
//#include<stdio.h>
//int main()
//{
//    char num[200] = "a";
//    scanf("%s", num);
//    for (int i = strlen(num) - 3; i > 0; i -= 3)
//    {
//        for (int j = strlen(num); j>=i; j--)
//        {
//            num[j ] = num[j-1];
//        }
//        num[i] = ',';
//    }
//    printf("%s", num);
//}
//#include <stdio.h>
//int main()
//{
//    char piao[10000]="a";
//    scanf("%s",piao);
//    int a=0,b=0;
//    for(int i=0;piao[i]!='0';i++)
//    {
//        if(piao[i]=='A')
//        {
//            a++;
//        }
//        if(piao[i]=='B')
//        {
//            b++;
//        }
//        if(piao[i]=='0')
//        {
//            break;
//        }
//    }
//    if(a>b)
//    {
//        printf("A\n");
//    }
//    else if(a<b)
//    {
//        printf("B\n");
//    }
//    else 
//    {
//        printf("E\n");
//    }
//}
//#include <stdio.h>
//int main()
//{
//    int n = 0, m = 0;
//    char arr[10000] = "a";
//    scanf("%d%d\n%s", &n, &m, arr);
//    for (int i = 0; i < m; i++)
//    {
//        int a = 0, b = 0;
//        char c1 = 'a', c2 = 'a';
//        scanf("%d %d %c %c", &a, &b, &c1, &c2);
//        for (int j = a - 1; j < b; j++)
//        {
//            if (arr[j] == c1)
//            {
//                arr[j] = c2;
//            }
//        }
//    }
//    printf("%s\n", arr);
//}
//#include <stdio.h>
//int geweishu(long long int n)
//{
//    int sum = 0;
//    while (n)
//    {
//        sum += n % 10;
//        n /= 10;
//    }
//    if (sum >= 10)
//        return geweishu(sum);
//    else
//        return sum;
//}
//int main()
//{
//    long long int n = 0;
//    scanf("%lld", &n);
//    int result = geweishu(n);
//    printf("%d", result);
//}
//#include <stdio.h>
//#include<math.h>
//int main()
//{
//    long long int n = 0;
//    scanf("%lld", &n);
//    long long int m = 10, sum = n;
//    while (n / m)
//    {
//        sum = (n / m) % 10 + sum * 10;
//        m *= 10;
//    }
//    int flag = 1;
//    for (int i = 2; i < sqrt(sum); i++)
//    {
//        if (sum % i == 0)
//        {
//            flag = 0;
//            break;
//        }
//    }
//    if (flag)
//    {
//        printf("prime\n");
//    }
//    else
//    {
//        printf("noprime\n");
//    }
//}
//#include<stdio.h>
//int jinzhi(int n)
//{
//    int sum1 = 0, sum0 = 0;
//    while (n)
//    {
//        int num = n % 2;
//        if (num == 1)
//        {
//            sum1++;
//        }
//        else
//        {
//            sum0++;
//        }
//        n /= 2;
//    }
//    if (sum1 % 2 == 0 && sum0 % 2 != 0)
//    {
//        return 1;
//    }
//    if (sum0 % 2 == 0 && sum1 % 2 != 0)
//    {
//        return 0;
//    }
//    if (sum0 % 2 == 0 && sum1 % 2 == 0)
//    {
//        return 10;
//    }
//}
//int main()
//{
//    int n = 0, arr[10000] = { 0 };
//    scanf("%d", &n);
//    for (int i = 0; i < n; i++)
//    {
//        scanf("%d", &arr[i]);
//        int result = jinzhi(arr[i]);
//        if (result == 1)
//        {
//            printf("1 ");
//        }
//        if (result == 0)
//        {
//            printf("0 ");
//        }
//        if (result == 10)
//        {
//            printf("10 ");
//        }
//    }
//}